import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
    int[] dx={1,-1,0,0};
    int[] dy={0,0,1,-1};
    int prev;
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if(image[sr][sc]==color) return image;
        prev=image[sr][sc];
        dfs1(image,sr,sc,color);
        return image;
    }
    public void dfs1(int[][] image,int sr,int sc,int color){
        image[sr][sc]=color;
        for(int i=0;i<4;i++){
            int x=dx[i]+sr;
            int y=dy[i]+sc;
            if(x>=0&&x<image.length&&y>=0&&y<image[0].length&&image[x][y]==prev){
                dfs(image,x,y,color);
            }
        }
    }
    boolean[] checkCol,checkDig1,checkDig2;
    List<List<String>>ret;
    char[][] path;
    int x;
    public List<List<String>> solveNQueens(int n) {
        checkCol=new boolean[n];
        checkDig1=new boolean[2*n];
        checkDig2=new boolean[2*n];
        path=new char[n][n];
        ret=new ArrayList<>();
        x=n;
        for(int i=0;i<n;i++){
            Arrays.fill(path[i],'.');
        }
        dfs(0);
        return ret;
    }
    public void dfs(int row){
        if(row==x){
            List<String> tmp=new ArrayList<>();
            for(int i=0;i<x;i++){
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
        }
        for(int col=0;col<x;col++){
            if(checkCol[col]==false&&checkDig1[row-col+x]==false&&checkDig2[row+col]==false){
                path[row][col]='Q';
                checkCol[col]=checkDig1[row-col+x]=checkDig2[row+col]=true;
                dfs(row+1);
                path[row][col]='.';
                checkCol[col]=checkDig1[row-col+x]=checkDig2[row+col]=false;
            }
        }
    }
}